{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Anagrams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #string #combinatorics #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #字符串 #组合数学 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countAnagrams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计同位异构字符串数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，它包含一个或者多个单词。单词之间用单个空格&nbsp;<code>' '</code>&nbsp;隔开。</p>\n",
    "\n",
    "<p>如果字符串 <code>t</code>&nbsp;中第 <code>i</code>&nbsp;个单词是 <code>s</code>&nbsp;中第 <code>i</code>&nbsp;个单词的一个&nbsp;<strong>排列</strong>&nbsp;，那么我们称字符串&nbsp;<code>t</code>&nbsp;是字符串&nbsp;<code>s</code>&nbsp;的同位异构字符串。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>\"acb dfe\"</code>&nbsp;是&nbsp;<code>\"abc def\"</code>&nbsp;的同位异构字符串，但是&nbsp;<code>\"def cab\"</code>&nbsp;和&nbsp;<code>\"adc bef\"</code>&nbsp;不是。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回<em>&nbsp;</em><code>s</code>&nbsp;的同位异构字符串的数目，由于答案可能很大，请你将它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong> 后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"too hot\"\n",
    "<b>输出：</b>18\n",
    "<b>解释：</b>输入字符串的一些同位异构字符串为 \"too hot\" ，\"oot hot\" ，\"oto toh\" ，\"too toh\" 以及 \"too oht\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"aa\"\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>输入字符串只有一个同位异构字符串。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 只包含小写英文字母和空格&nbsp;<code>' '</code>&nbsp;。</li>\n",
    "\t<li>相邻单词之间由单个空格隔开。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-anagrams](https://leetcode.cn/problems/count-anagrams/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-anagrams](https://leetcode.cn/problems/count-anagrams/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"too hot\"', '\"aa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = mul = 1\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % MOD\n",
    "                ans = ans * i % MOD\n",
    "        return ans * pow(mul, -1, MOD) % MOD\n",
    "\n",
    "\n",
    "            # 费马小定理"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        p = 10**9 + 7\n",
    "        hetero_num = 1\n",
    "        words = s.split()\n",
    "        for word in words:\n",
    "            alphabet_num = {}\n",
    "            word_len = len(word)\n",
    "            for char in word:\n",
    "                alphabet_num[char]=alphabet_num.get(char,0) + 1\n",
    "            hetero_word_num = 1\n",
    "            for i in alphabet_num.values():\n",
    "                hetero_word_num *= comb(word_len, i)\n",
    "                word_len -= i\n",
    "            hetero_word_num %= p\n",
    "            hetero_num *= hetero_word_num\n",
    "            hetero_num %= p\n",
    "        return hetero_num\n",
    "\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = mul = 1\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % MOD\n",
    "                ans = ans * i % MOD\n",
    "        return ans * pow(mul, -1, MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict,deque\n",
    "from functools import cache\n",
    "import heapq\n",
    "from sortedcontainers import SortedDict,SortedList\n",
    "from collections import Counter\n",
    "\n",
    "mod  = 10**9+7\n",
    "def quickPow(x,y):\n",
    "    ret =1\n",
    "    cur = x \n",
    "    while y >0:\n",
    "        if y & 1:\n",
    "            ret = ret * cur % mod\n",
    "        cur = cur *cur % mod\n",
    "        y = y //2\n",
    "    return ret\n",
    "@cache\n",
    "def inv(x):\n",
    "    return quickPow(x,mod-2)\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ans,mul = 1,1\n",
    "        for word in s.split(\" \"):\n",
    "            c = Counter()\n",
    "            for i,a in enumerate(word,1):\n",
    "                c[a] +=1\n",
    "                mul *= c[a]\n",
    "                ans *= i\n",
    "                mul,ans = mul %mod, ans%mod \n",
    "        return (ans * inv(mul))%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = Counter()\n",
    "        ans = mul = 1\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % MOD\n",
    "                ans = ans * i % MOD\n",
    "        return ans * pow(mul, -1, MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        a, b = 1, 1\n",
    "        MOD = 10**9 + 7\n",
    "        for t in s.split():\n",
    "            cnt  = Counter()\n",
    "            for i,c in enumerate(t):\n",
    "                a = a * (i+1) % MOD\n",
    "                cnt[c] += 1\n",
    "                b = b * cnt[c] % MOD\n",
    "        return a * pow(b, -1, MOD) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        # 给定字符串的同份异构词数\n",
    "        # 组合计数\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = mul = 1\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % MOD\n",
    "                ans = ans * i % MOD\n",
    "        return ans * pow(mul, -1, MOD) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        from collections import Counter\n",
    "        res = 1\n",
    "        for word in s.split(' '):\n",
    "            n, count = len(word), Counter(word)\n",
    "            for w in count:\n",
    "                res *= math.comb(n, count[w])\n",
    "                res %= 1000000007\n",
    "                n -= count[w]\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD=10**9+7\n",
    "        a=b=1\n",
    "        for t in s.split():\n",
    "            cnt=Counter()\n",
    "            for i ,c in enumerate(t,1):\n",
    "                a=a*i%MOD\n",
    "                cnt[c]+=1\n",
    "                b=b*cnt[c]%MOD\n",
    "        return a*pow(b,-1,MOD)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        for x in s.split(' '):\n",
    "            n = len(x)\n",
    "            for v in Counter(x).values():\n",
    "                ans *= comb(n, v)\n",
    "                n -= v\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = mul = 1\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % MOD\n",
    "                ans = ans * i % MOD\n",
    "        return ans * pow(mul, MOD - 2, MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def helper(s):\n",
    "            n = len(s)\n",
    "            count = Counter(s)\n",
    "            res = 1\n",
    "            for i in range(1, n+1):\n",
    "                res *= i\n",
    "                res %= MOD\n",
    "            chu = 1\n",
    "            for c in count.values():\n",
    "                for i in range(1, c+1):\n",
    "                    chu *= i\n",
    "                    chu %= MOD\n",
    "            return res * pow(chu, -1, MOD) % MOD\n",
    "        \n",
    "        res = 1\n",
    "        for cur_s in s.split():\n",
    "            res *= helper(cur_s)\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # too hot\n",
    "        # 把每个单词的方案数算出来，用乘法原理相乘\n",
    "        # too -> 3!/2! = 3\n",
    "        # hot -> 3! = 6\n",
    "        # aab -> 3!/2! = 3\n",
    "        # 分子分母分开计算\n",
    "        # 3!*3!*3! / 2!*2! = 216/4 = 54\n",
    "        # a表示 t字符串全排列个数\n",
    "        # b表示 t字符串考虑相同字符的全排列个数\n",
    "        a = b = 1\n",
    "        for t in s.split(\" \"):\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(t, 1):\n",
    "                a = a * i % MOD\n",
    "                cnt[c] += 1\n",
    "                b = b * cnt[c] % MOD\n",
    "        return a * pow(b, -1, MOD) % MOD  # 费马小定理"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = mul = 1\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % MOD\n",
    "                ans = ans * i % MOD\n",
    "        return ans * pow(mul, -1, MOD) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        s = s.split()\n",
    "        \n",
    "        res = 1\n",
    "        \n",
    "        for word in s:\n",
    "            n = len(word)\n",
    "            counter = Counter(word)\n",
    "            cnt = 1\n",
    "            for ch, k in counter.items():\n",
    "                if k > 1:\n",
    "                    cnt = ((cnt % MOD) * (comb(n, k) % MOD)) % MOD\n",
    "                    n -= k\n",
    "    \n",
    "            m = sum(val == 1 for val in counter.values())\n",
    "        \n",
    "            cnt = ((cnt % MOD) * (factorial(m) % MOD)) % MOD\n",
    "            \n",
    "            res = ((res % MOD) * (cnt % MOD)) % MOD\n",
    "            \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = mul = 1\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % MOD\n",
    "                ans = ans * i % MOD\n",
    "        return ans * pow(mul, -1, MOD) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = mul = 1\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % MOD\n",
    "                ans = ans * i % MOD\n",
    "        return ans * pow(mul, -1, MOD) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def countAnagrams(self, s: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       ans = mul = 1\n",
    "       for s in s.split():\n",
    "           cnt = Counter()\n",
    "           for i, c in enumerate(s, 1):\n",
    "               cnt[c] += 1\n",
    "               mul = mul * cnt[c] % MOD\n",
    "               ans = ans * i % MOD\n",
    "       return ans * pow(mul, -1, MOD) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ans = mul = 1\n",
    "        mod = int(1e9+7)\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % mod\n",
    "                ans = ans * i % mod\n",
    "        \n",
    "        return ans * pow(mul, -1, mod) % mod\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # too hot\n",
    "        # 把每个单词的方案数算出来，用乘法原理相乘\n",
    "        # too -> 3!/2! = 3\n",
    "        # hot -> 3! = 6\n",
    "        # aab -> 3!/2! = 3\n",
    "        # 分子分母分开计算\n",
    "        # 3!*3!*3! / 2!*2! = 216/4 = 54\n",
    "        # a表示 t字符串全排列个数\n",
    "        # b表示 t字符串考虑相同字符的全排列个数\n",
    "        a = b = 1\n",
    "        for t in s.split(\" \"):\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(t, 1):\n",
    "                a = a * i % MOD\n",
    "                cnt[c] += 1\n",
    "                b = b * cnt[c] % MOD\n",
    "        return a * pow(b, -1, MOD) % MOD  # 费马小定理"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = mul = 1\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                cnt[c] += 1\n",
    "                mul = mul * cnt[c] % MOD\n",
    "                ans = ans * i % MOD\n",
    "        return ans * pow(mul, -1, MOD) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        def k4s(s):\n",
    "            d = collections.defaultdict(int)\n",
    "            n = len(s)\n",
    "            for ch in s:\n",
    "                d[ch] += 1\n",
    "            ans = 1\n",
    "            for k in d.keys():\n",
    "                v = d[k]\n",
    "                ans = ans * math.comb(n, v)\n",
    "                n -= v\n",
    "            return ans\n",
    "        strs = s.split()\n",
    "        ans = 1\n",
    "        for st in strs:\n",
    "            ans = (ans * k4s(st)) % 1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        for x in s.split(' '):\n",
    "            n = len(x)\n",
    "            for v in Counter(x).values():\n",
    "                ans *= comb(n, v)\n",
    "                n -= v\n",
    "        return ans % (10**9 + 7)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        count = 1\n",
    "        ans = 1\n",
    "        mod = 10**9+7\n",
    "        for s in s.split():\n",
    "            cnt = Counter()\n",
    "            for i, c in enumerate(s, 1):\n",
    "                print(i)\n",
    "                cnt[c] += 1\n",
    "                count = count * i % mod\n",
    "                ans = ans * cnt[c] % mod\n",
    "        return count * pow(ans,-1,mod) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD=10**9+7\n",
    "        words=list(s.split())\n",
    "        #print(words)\n",
    "        res=mul=1\n",
    "        for word in words:\n",
    "            \n",
    "            cnt=Counter()\n",
    "            for i,c in enumerate(word,1):\n",
    "                cnt[c] +=1\n",
    "                mul =mul*cnt[c]%MOD\n",
    "                res=res*i%MOD\n",
    "        return res*pow(mul,-1,MOD)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        for w in s.split(' '):\n",
    "            cur = factorial(len(w))\n",
    "            for c in Counter(w).values():\n",
    "                cur //= factorial(c)\n",
    "            ans = (ans * cur) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans, tmp = 1, 1\n",
    "        fac = cache(math.factorial)\n",
    "        for ss in s.split(' '):\n",
    "            c = Counter(ss)\n",
    "            tmp *= reduce(mul, [fac(c[key]) for key in c])\n",
    "            tmp %= mod\n",
    "            ans *= fac(len(ss))\n",
    "            ans %= mod\n",
    "        return (ans * pow(tmp, -1, mod)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        res = 1\n",
    "        for i in s.split():\n",
    "            a = Counter(i)\n",
    "            l = factorial(len(i))\n",
    "            for k, v in a.items():\n",
    "                l = l // factorial(v)\n",
    "            res = (res * l)\n",
    "        return res % ((10 ** 9) + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ret=1\n",
    "        mod=10**9+7\n",
    "        for i in s.split():\n",
    "            c=Counter(i)\n",
    "            redun=[v for k,v in c.items() if v>1]\n",
    "            #print(redun,i)\n",
    "            ret*=math.factorial(len(i))\n",
    "            ret%=mod\n",
    "            #print(ret)\n",
    "            while redun:\n",
    "                t=redun.pop()\n",
    "                ret*=pow(math.factorial(t),-1,mod)%mod\n",
    "            #print(ret)\n",
    "        return ret%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        def cal(s):\n",
    "            tot = math.factorial(len(s))\n",
    "            c = Counter(s)\n",
    "            for v in c:\n",
    "                cur = math.factorial(c[v])\n",
    "                tot //= cur\n",
    "            return tot\n",
    "        s = s.split(' ')\n",
    "        ans = 1\n",
    "        for t in s:\n",
    "            ans *= cal(t)\n",
    "            ans %= (10 ** 9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from math import factorial\n",
    "from typing import List\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        # 拆分字符串为单词列表\n",
    "        words = s.split(\" \")\n",
    "        \n",
    "        # 初始化结果为 1\n",
    "        result = 1\n",
    "        \n",
    "        # 遍历每个单词\n",
    "        for word in words:\n",
    "            # 计算单词长度\n",
    "            n = len(word)\n",
    "            \n",
    "            # 获取单词中每个字符的个数\n",
    "            counter = Counter(word)\n",
    "            \n",
    "            # 计算单词的排列数，即 n! / (a! * b! * ...)\n",
    "            word_anagrams = factorial(n)\n",
    "            for count in counter.values():\n",
    "                word_anagrams //= factorial(count)\n",
    "            \n",
    "            # 更新结果\n",
    "            result *= word_anagrams\n",
    "            result %= MOD  # 取模\n",
    "        \n",
    "        return result\n",
    "\n",
    "# 测试\n",
    "sol = Solution()\n",
    "print(sol.countAnagrams(\"abc def\"))  # 输出应为 6 * 6 = 36\n",
    "print(sol.countAnagrams(\"aabb cc\"))  # 输出应为 6 * 2 = 12\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        s = s.split()\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        for word in s:\n",
    "            cnt = factorial(len(word))\n",
    "            cnts = Counter(word).values()\n",
    "            for val in cnts:\n",
    "                cnt //= factorial(val)\n",
    "\n",
    "            res = (res * cnt) % MOD \n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        arr = s.split()\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = 1\n",
    "        for e in arr:\n",
    "            le = len(e)\n",
    "            res *= factorial(le)\n",
    "            dic = Counter(e)\n",
    "            for v in dic.values():\n",
    "                res //= factorial(v)\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        MOD=10**9 + 7\n",
    "        res=1\n",
    "        for word in s.split(\" \"):\n",
    "            t=math.factorial(len(word))\n",
    "            for n in Counter(word).values():\n",
    "                t//=math.factorial(n)\n",
    "            res*=t\n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        s = s.split()\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        for word in s:\n",
    "            cnt = factorial(len(word))\n",
    "            cnts = Counter(word).values()\n",
    "            for val in cnts:\n",
    "                cnt //= factorial(val)\n",
    "\n",
    "            res = (res * cnt) % MOD \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        M = 10**9+7\n",
    "        res = 1\n",
    "        for w in s.split():\n",
    "            l = len(w)\n",
    "            c = Counter(w)\n",
    "            res = res * perm(l) // (reduce(mul, (perm(v) for v in c.values() if v), 1)) % M\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        s = s.split()\n",
    "        \n",
    "        res = 1\n",
    "\n",
    "        for word in s:\n",
    "            cnt = factorial(len(word))\n",
    "            cnts = Counter(word).values()\n",
    "            for val in cnts:\n",
    "                cnt = (cnt % MOD * pow(factorial(val), -1, MOD)) % MOD \n",
    "\n",
    "            res = (res * cnt) % MOD \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "\n",
    "        ans = 1\n",
    "        n = len(s)\n",
    "        g = [0] * (n + 1)\n",
    "        g[0] = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n + 1):\n",
    "            g[i] = g[i - 1] * i % mod\n",
    "        for word in s.split(' '):\n",
    "            cnt = Counter(word)\n",
    "            m = len(word)\n",
    "            cur = g[m]\n",
    "            for k, v in cnt.items():\n",
    "                if v > 1:\n",
    "                    cur = cur * pow(g[v], -1, mod) % mod\n",
    "            ans *= cur\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "\n",
    "        ans = 1\n",
    "        n = len(s)\n",
    "        g = [0] * (n + 1)\n",
    "        g[0] = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n + 1):\n",
    "            g[i] = g[i - 1] * i % mod\n",
    "        for word in s.split(' '):\n",
    "            cnt = Counter(word)\n",
    "            m = len(word)\n",
    "            cur = g[m]\n",
    "            for k, v in cnt.items():\n",
    "                cur = cur * pow(g[v], -1, mod) % mod\n",
    "            ans *= cur\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9 + 7\n",
    "A = [1] * 100001\n",
    "for i in range(2, 100001):\n",
    "    A[i] = A[i - 1] * i % mod\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ans, mul = 1, 1\n",
    "        for w in s.split():\n",
    "            ans = ans * A[len(w)] % mod\n",
    "            cnt = Counter(w)\n",
    "            for c in cnt.values():\n",
    "                mul = mul * A[c] % mod\n",
    "        return ans * pow(mul, -1, mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "MX = 10**5\n",
    "fact = [1] * (MX+1)\n",
    "for x in range(1, MX+1):\n",
    "    fact[x] = fact[x-1] * x % MOD\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        for word in s.split():\n",
    "            cnt = defaultdict(int)\n",
    "            for ch in word:\n",
    "                cnt[ch] += 1\n",
    "            res = fact[len(word)]\n",
    "            for v in cnt.values():\n",
    "                res = res * pow(fact[v], -1, MOD) % MOD\n",
    "            ans = ans * res % MOD\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10 ** 5 + 1\n",
    "dp = [1] * M\n",
    "mod = 10 ** 9 + 7\n",
    "for i in range(1, M):\n",
    "    dp[i] = dp[i - 1] * i % mod\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        s_l = s.split(\" \")\n",
    "        ans = 1\n",
    "        for i in s_l:\n",
    "            n = len(i)\n",
    "            c = Counter(i)\n",
    "            cnt = dp[n]\n",
    "            # print(\"cnt\", cnt)\n",
    "            for k, v in c.items():\n",
    "                if v > 1:\n",
    "                    cnt = (cnt * pow(dp[v], mod - 2, mod)) % mod\n",
    "                    # print(\"mid cnt\", v, cnt)\n",
    "            # print(\"after cnt\", cnt)\n",
    "            ans = (ans * cnt) % mod\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9 + 7\n",
    "A = [1] * 100001\n",
    "for i in range(2, 100001):\n",
    "    A[i] = A[i - 1] * i % mod\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ans, mul = 1, 1\n",
    "        for w in s.split():\n",
    "            ans = ans * A[len(w)] % mod\n",
    "            cnt = Counter(w)\n",
    "            for c in cnt.values():\n",
    "                mul = mul * A[c] % mod\n",
    "        return ans * pow(mul, -1, mod) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Combinatorics:\n",
    "    def __init__(self, n, mod):\n",
    "        # 模板：求全排列组合数，使用时注意 n 的取值范围\n",
    "        n += 10\n",
    "        self.perm = [1] * n\n",
    "        self.rev = [1] * n\n",
    "        self.mod = mod\n",
    "        for i in range(1, n):\n",
    "            # 阶乘数 i! 取模\n",
    "            self.perm[i] = self.perm[i - 1] * i\n",
    "            self.perm[i] %= self.mod\n",
    "        self.rev[-1] = self.mod_reverse(self.perm[-1], self.mod)  # 等价于pow(self.perm[-1], -1, self.mod)\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            self.rev[i] = (self.rev[i + 1] * (i + 1) % mod)  # 阶乘 i! 取逆元\n",
    "        self.fault = [0] * n\n",
    "        self.fault_perm()\n",
    "        return\n",
    "\n",
    "    def ex_gcd(self, a, b):\n",
    "        # 扩展欧几里得求乘法逆元\n",
    "        if b == 0:\n",
    "            return 1, 0, a\n",
    "        else:\n",
    "            x, y, q = self.ex_gcd(b, a % b)\n",
    "            x, y = y, (x - (a // b) * y)\n",
    "            return x, y, q\n",
    "\n",
    "    def mod_reverse(self, a, p):\n",
    "        x, y, q = self.ex_gcd(a, p)\n",
    "        if q != 1:\n",
    "            raise Exception(\"No solution.\")   # 逆元要求a与p互质\n",
    "        else:\n",
    "            return (x + p) % p  # 防止负数\n",
    "\n",
    "    def comb(self, a, b):\n",
    "        if a < b:\n",
    "            return 0\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a] * self.rev[b] * self.rev[a - b]\n",
    "        return res % self.mod\n",
    "\n",
    "    def factorial(self, a):\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a]\n",
    "        return res % self.mod\n",
    "\n",
    "    def fault_perm(self):\n",
    "        # 求错位排列组合数\n",
    "        self.fault[0] = 1\n",
    "        self.fault[2] = 1\n",
    "        for i in range(3, len(self.fault)):\n",
    "            self.fault[i] = (i - 1) * (self.fault[i - 1] + self.fault[i - 2])\n",
    "            self.fault[i] %= self.mod\n",
    "        return\n",
    "\n",
    "    def inv(self, n):\n",
    "        # 求 pow(n, -1, mod)\n",
    "        return self.perm[n - 1] * self.rev[n] % self.mod\n",
    "\n",
    "    def catalan(self, n):\n",
    "        # 求卡特兰数\n",
    "        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod\n",
    "\n",
    "\n",
    "mod = 10**9 + 7\n",
    "cb = Combinatorics(10**5, mod)\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        for word in s.split(\" \"):\n",
    "            cnt = Counter(word)\n",
    "            cur = 1\n",
    "            m = len(word)\n",
    "            for w in cnt:\n",
    "                cur *= cb.comb(m, cnt[w])\n",
    "                m -= cnt[w]\n",
    "            cur %= mod\n",
    "            ans *= cur\n",
    "            ans %= mod\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\r\n",
    "from functools import reduce\r\n",
    "\r\n",
    "mod = 1000000007\r\n",
    "f = [0] * 100001\r\n",
    "finv = [0] * 100001\r\n",
    "\r\n",
    "def fact(num: int) -> int:\r\n",
    "    if num < 2: return 1\r\n",
    "    if f[num] == 0:\r\n",
    "        f[num] = (num * fact(num - 1)) % mod\r\n",
    "    return f[num]\r\n",
    "\r\n",
    "def factinv(num: int) -> int:\r\n",
    "    if finv[num] == 0:\r\n",
    "        finv[num] = pow(fact(num), mod - 2, mod)\r\n",
    "    return finv[num]\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def countAnagrams(self, s: str) -> int:\r\n",
    "        return reduce(lambda x, y:\r\n",
    "                    x * reduce(lambda a, b:\r\n",
    "                        a * factinv(b) % mod,\r\n",
    "                        Counter(y).values(),\r\n",
    "                        fact(len(y))) % mod,\r\n",
    "                    s.split(' '),\r\n",
    "                    1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "cache = defaultdict(int)\n",
    "cache[1] = 1\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        s = s.split()\n",
    "\n",
    "        def dfs(x: int, m: int) -> int:\n",
    "            if x == 1:\n",
    "                return 1\n",
    "\n",
    "            if cache[x] == 0:\n",
    "                cache[x] = (x % m * dfs(x - 1, m) % m) % m\n",
    "\n",
    "            return cache[x]\n",
    "\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        for word in s:\n",
    "            counter = Counter(word)\n",
    "            cnt = dfs(len(word), MOD)\n",
    "            for val in counter.values():\n",
    "                cnt = (cnt % MOD * pow(dfs(val, MOD), -1, MOD)) % MOD \n",
    "\n",
    "            res = (res * cnt) % MOD \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "cache = defaultdict(int)\n",
    "cache[1] = 1\n",
    "\n",
    "class Solution:\n",
    "    def countAnagrams(self, s: str) -> int:\n",
    "        s = s.split()\n",
    "\n",
    "        def mod_factorial(x: int) -> int:\n",
    "            if x == 1:\n",
    "                return 1\n",
    "\n",
    "            if cache[x] == 0:\n",
    "                cache[x] = (x % MOD * mod_factorial(x - 1) % MOD) % MOD\n",
    "\n",
    "            return cache[x]\n",
    "\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        for word in s:\n",
    "            counter = Counter(word)\n",
    "            cnt = mod_factorial(len(word))\n",
    "            for val in counter.values():\n",
    "                cnt = (cnt % MOD * pow(mod_factorial(val), -1, MOD)) % MOD \n",
    "\n",
    "            res = (res * cnt) % MOD \n",
    "\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
